1. Field of the Invention
This invention generally relates to real-time, knowledge-based control of both small-scale systems and large-scale systems. More particularly, this invention relates to computer-based control of systems distributed in space and/or time that are composed of components whose logical (set-based) and evolution (continuum-based) behaviors are controlled by a collection of agents. This invention provides general purpose methods for incremental, reactive construction of the composed system through on-line generation of software by each agent. The generated software governs individual agent behavior and provides near-optimal compliance with declared logical and evolution constraints on local and global system goals, sensor values, and performance characteristics.
2. Discussion of the Related Technology
Computer-controlled systems are collections of components used either to advise humans in executing their control responsibilities or to autonomously execute appropriate control actions. Computer-controlled systems may also have a combination of both advisory components and autonomous components.
Typical components of distributed, real-time computer-controlled systems include computers, communication networks, software, sensors (analog-to-digital transducers), and actuators (digital-to-analog transducers). Systems are controlled to achieve desired high-level event-based goals (such as safety goals or quality goals) often expressed as rules of desired behavior and are controlled to achieve desired low-level evolution-based goals (such as accurate rate of change of angular position or precision control of displacement velocity) often expressed as differential or difference equations.
Current engineering environments provide support for conducting extensive experiments for trying out various control mechanisms. Major efforts have been conducted over the past few decades to provide ever more precise statements of system constraints and ever more powerful simulation environments for conducting more extensive combinations of experiments to discover failure modes of the contemplated control mechanisms. As systems are being analyzed, designed, implemented, and maintained, these extensive experiments conducted in the engineering environment are used to perform verification, validation, and accreditation of the models and algorithms used by the computer-controlled system to achieve autonomous or semi-autonomous (human-in-the-loop) control of the distributed system.
The existing technical approach has met with great success for small-scale systems. However, according to the U.S. Department of Commerce, as many as seventy to ninety percent of real-time systems fail to ever meet their goals and be deployed. Moreover, for those systems that are deployed, the fraction of initial system cost attributable to software continues to rise, accounting for between thirty to ninety percent of initial acquisition costs. A primary cause of failure in constructing large-scale, distributed systems is the difficulty of synchronizing real-time processes.
The best existing technology relies on engineering experience and heuristics to build computer-controlled systems that combine logical constraints, geometric constraints, and evolution constraints on system behavior. Verification, validation, and accreditation of these systems is achieved through expensive and inconclusive development efforts that attempt to discover and correct system failure modes through a series of simulation or benchmark experiments followed by correction of discovered failure modes. As indicated above, large-scale, real-time control efforts often fail and the projects are abandoned after expenditure of significant resources. Those that are successful are difficult to update, because the series of verification, validation, and accreditation experiments must be repeated whenever the system is changed.
The invention improves over the current technology through the generation of control software that meets declared constraints. The technology is based on rigorous mathematical results that establish that the approach is sound (will not prove a theorem that contradicts assertions in the knowledge base) and complete (will prove theorems that generate actions to cause the system state to reach (within declared closeness criteria) any point that is in the range of points described by the knowledge base). This formal theoretical result, and the practical implementation of the result in the invention, enables the incremental construction of large-scale, distributed, real-time control systems from trusted components. Thus, to the extent that an existing component has achieved a degree of trust, the invention enables inclusion of that component in a larger system, without repeating the previous experiments. Moreover, for smaller well-understood systems constructed from legacy, product-line applications, the invention enables reliable implementation of a wider variability in system parameters.
There are no products similar to the Multiple-Agent Hybrid Control Architecture (MAHCA). Features of MAHCA include:
1. MAHCA uses general descriptions of system state that combine logical and evolution constraints on system behavior. The best commercial simulation products have supported such combined descriptions of system behavior for many years. Examples of commercial simulation systems include SIMNON and ACSL, both of which support nonlinear system descriptions, discovery of system equilibrium points, and linearization about system equilibria for design of linear controllers. The best experimental prototype is DSTOOL from Cornell University, which uses a system description closest to that of MAHCA. A recent Ph.D. thesis by Mats Andersson from Lund Institute of Technology discusses simulation of hybrid systems. The thesis describes the systems modeling language Omola and the simulation system OmSim. While these products and experimental systems support discovery of system behavior, including discovery of failure modes, they do not support creation of controllers to compensate for undesired behaviors.
2. MAHCA's logical and evolution description of system behavior delivers cumulative control solutions. Commercial products for design of control systems exist, including some that generate control code from experiments. The best commercial systems are MATLAB, MATRIX-X, and BEACON. The best experimental prototypes are ANDECS from Germany, HONEY-X from Honeywell, and METL from University of Waterloo. METL is closest in spirit to MAHCA in that METL supports both logical and evolution descriptions of system behavior and delivery of control solutions that meet logical and evolution constraints. METL, however, relies on experimental discovery of failure modes and application of engineering heuristics to construct combined solutions, as do all other control design tools currently available.
3. MAHCA supports a system for solving both linear and nonlinear scheduling of events. Commercial products exist for scheduling discrete sequences of events. An extension to the G2 product from GENSYM Corp. is currently being marketed as an optimal scheduling package for discrete manufacturing. This product, like other scheduling packages, relies on solution of a linear approximation to what is known to be a nonlinear problem. MAHCA solves the nonlinear scheduling problem as well as its linear approximation.
4. MAHCA uses a general purpose architecture descriptor. General purpose architectures for large-scale, real-time systems have been under development for some time. The NASREM architecture, a joint development of the National Bureau of Standards and the National Aeronautics and Space Administration, was published as an open standard in 1989. This reference architecture for real-time, distributed control has been used as a starting point for several large-scale systems as well as the beginning of the Next Generation Controller project and the beginning of two projects in component-based programming supported by the Advanced Research Projects Agency (ARPA) Domain-Specific Software Architecture (DSSA) project. One of these projects has the best experimental prototype for declaring system architectures, the ARDEC-TEKNOWLEDGE (ARTEK) model. Neither NASREM nor ARTEK, however, support development of control programs for the systems described by their architectural syntax. MAHCA can use either NASREM or ARTEK syntax to describe reference architectures for large-scale systems and can also can generate control software to execute actions necessary to meet the design goals of the architecture applications. Also, while both NASREM and ARTEC support declarations of synchronization requirements for large-scale distributed system, neither support construction of control solutions that achieve the required synchronization.
MAHCA provides technology for flexible implementations of heterogeneous systems which substantially expand on the capabilities of real-time control architectures envisioned by the National Institute of Standards and Technology (NIST) and the National Aeronautics and Space Administration (NASA) in "NASA/NBS Standard Reference Model for Telerobot Control System Architecture (NASREM)," NIST (formerly NBS) Technical Note 1235, April 1989. The NASREM experimentation-based architecture represents the most logical arrangement of tools for experimental development of intelligent, real-time, computer-controlled systems. The NASREM architecture has been one of the most widely implemented architectures for large-scale systems and was the starting point for real-time, component-based control research being conducted by the Department of Defense. NASREM has several very useful features including:
1. NASREM supports separation of complex real-time systems into a fixed hierarchy based upon lower levels of the hierarchy being implemented at faster time scales and higher levels in the hierarchy being implemented at slower time scales. The time scales nominally vary from several hours of observations of system evolution at the slowest time scale to several milliseconds of observations of system evolution at the fastest time scale.
2. NASREM supports a further separation of complex, real-time systems into fixed heterarchical partitions at each layer in the hierarchy which correspond to components for a fixed, closed-loop approach for control of each layer according to a sense-decide-act paradigm of:
a. Sense the state of the system at each layer (time scale) in the hierarchy. Analog-to-digital transducers are used to automatically sense and provide inputs at the lowest levels in the hierarchy while user interfaces are used to obtain human queries, response to system queries, or decisions at the highest layers in the hierarchy. PA1 b. Decide which action or plan should be implemented. Scheduling algorithms for sequential machines used for a discrete-event system, switching tables experimentally produced for accomplishing gain-scheduling for closed-loop control algorithms appropriate for different operating modes, or adaptive control algorithms appropriate for use around well-defined operating points are used to decide what actions are to be taken at the lowest layers in the hierarchy. PA1 c. Act to execute the appropriate action for the current state of the system at each layer in the hierarchy. Since lower levels operate at faster time scales than higher levels in the hierarchy (the lowest level being several orders of magnitude faster than the highest level), many actions are taken at a lower level for each action taken at a higher level.
Each heterarchical partition proceeds at a fixed rate to implement the sense-decide-act cycle for the level it controls. The rate can be designed into the system based upon the performance requirements of the users, or the rate may be experimentally determined based upon the physical requirements of existing processes. Each layer accesses a global knowledge base that contains the knowledge of the current state of the system and constraints concerning decisions that can be made for the next cycle.
3. NASREM separates system behaviors into major logical activities being conducted based upon nominal partitioning according to system time scales. This supports a deliberate design of adding higher-level logical functionality in layers from the simplest to the most elaborate as the complex system is incrementally designed, prototyped, assembled, tested, and commissioned.
NASREM, and other architectures based upon conducting extensive experiments to implement complex, large-scale systems, has been a successful engineering approach. However, as systems grow in size and complexity, this technology has been increasingly less effective in achieving successful implementations.